package com.future.offer;

/**
 * Description:
 *
 * @author weiruibai.vendor
 * Date: 2023/1/19 16:21
 */
public class Solution_099 {

    private static Solution_099 instance = new Solution_099();

    public static void main(String[] args) {

    }

    /**
     * 上到下
     *
     * @param grid
     * @return
     */
    public int minPathSum_dp(int[][] grid) {
        int N = grid.length;
        int M = grid[0].length;
        int[][] dp = new int[N][M];
        dp[0][0] = grid[0][0];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int val = 0;
                if (i > 0 && j > 0) {
                    val = Math.min(dp[i][j - 1], dp[i - 1][j]);
                } else {
                    // 左
                    if (j > 0) {
                        val = dp[i][j - 1];
                    }
                    // 上
                    if (i > 0) {
                        if (val == 0) {
                            /**
                             * 说明j==0，此时val是默认值，
                             * 如果直接Math.min(dp[i - 1][j], val)
                             * 相当于Math.min(dp[i - 1][j], 0) 即结果为0
                             * 根据grid[i][j]>=0可知，不符合要求
                             */
                            val = dp[i - 1][j];
                        } else {
                            val = Math.min(dp[i - 1][j], val);
                        }
                    }
                }
                dp[i][j] = val + grid[i][j];
            }
        }
        return dp[N - 1][M - 1];
    }


    /**
     * 暴力超时
     * 从下到上
     *
     * @param grid
     * @return
     */
    public int minPathSum_v1(int[][] grid) {
        return process_v2(grid, 0, 0);
    }

    private int process_v2(int[][] grid, int i, int j) {
        if (i >= grid.length || j >= grid[0].length) {
            return Integer.MAX_VALUE;
        }
        if (i == grid.length - 1 && j == grid[0].length - 1) {
            return grid[i][j];
        }
        int m1 = Integer.MAX_VALUE;
        int m2 = Integer.MAX_VALUE;
        if (i < grid.length && j < grid[0].length) {
            m1 = process_v2(grid, i, j + 1);
            m2 = process_v2(grid, i + 1, j);
        } else {
            if (i == grid.length - 1) {
                // 只能向右
                m1 = process_v2(grid, i, j + 1);
            }
            if (j == grid[0].length - 1) {
                // 只能向下
                m2 = process_v2(grid, i + 1, j);
            }
        }
        return Math.min(m1, m2) + grid[i][j];
    }

    /**
     * 暴力超时
     * 从上到下
     *
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        process(grid, 0, 0, 0);
        return ans;
    }

    int ans = Integer.MAX_VALUE;

    private void process(int[][] grid, int i, int j, int sum) {
        if (i >= grid.length || j >= grid[0].length) {
            return;
        }
        if (i == grid.length - 1 && j == grid[0].length - 1) {
            ans = Math.min(sum + grid[i][j], ans);
            return;
        }
        if (i < grid.length && j < grid[0].length) {
            process(grid, i, j + 1, sum + grid[i][j]);
            process(grid, i + 1, j, sum + grid[i][j]);
        } else {
            if (i == grid.length - 1) {
                // 只能向右
                process(grid, i, j + 1, sum + grid[i][j]);
            }
            if (j == grid[0].length - 1) {
                // 只能向下
                process(grid, i + 1, j, sum + grid[i][j]);
            }
        }
    }

}
